#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> ret(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; i++)
        {
            ret[0][i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                ret[i][j] = min(ret[i - 1][j], min(ret[i - 1][j - 1], ret[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int my_min = INT_MAX;
        for (int i = 1; i <= n; i++)
        {
            if (my_min > ret[n][i])
            {
                my_min = ret[n][i];
            }
        }
        return my_min;
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int x = INT_MAX;
                int y = INT_MAX;
                if (i - 1 >= 0)
                {
                    x = ret[i - 1][j];
                }
                if (j - 1 >= 0)
                {
                    y = ret[i][j - 1];
                }
                if (x == INT_MAX && y == INT_MAX)
                {
                    x = 0;
                }
                ret[i][j] = min(x, y) + grid[i][j];
            }
        }
        return ret[m - 1][n - 1];
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> ret(m + 1, vector<int>(n + 1, INT_MAX));
        ret[0][1] = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                ret[i][j] = min(ret[i - 1][j], ret[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return ret[m][n];
    }
};

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> ret(m + 1, vector<int>(n + 1, INT_MAX));
        ret[m - 1][n] = ret[m][n - 1] = 1;
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                ret[i][j] = min(ret[i + 1][j], ret[i][j + 1]) - dungeon[i][j];
                ret[i][j] = max(1, ret[i][j]);
            }
        }
        return ret[0][0];
    }
};

class Solution {
public:
    int massage(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        vector<int> f(n);
        vector<int> g(n);
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};